class code3 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] ret = new int[nums.length-k+1];
        LinkedList<Integer> q = new LinkedList<>();

        for(int right=0; right <nums.length ;right++) {
            //去除老元素
            while(!q.isEmpty() && nums[right] >= nums[q.peekLast()]) {
                q.pollLast();
            }
            //加入队列
            q.addLast(right);

            //判断元素是否出界
            int left = right-k+1;
            if(q.peek() < left) {
                q.poll();
            }
            //加入ret：当窗口右边界right+1大于等于窗口大小k
            if(right+1 >= k) {
                ret[left] = nums[q.peek()];
            }
        }
        return ret;
    }
}